//
// Created by Administrator on 2021/5/7.
//

/*
有效括号字符串为空("")、"(" + A + ")"或A + B，其中A 和B都是有效的括号字符串，+代表字符串的连接。
 例如，""，"()"，"(())()"和"(()(()))"都是有效的括号字符串。

如果有效字符串S非空，且不存在将其拆分为S = A+B的方法，我们称其为原语（primitive），其中A 和B都是非空有效括号字符串。

给出一个非空有效字符串S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中P_i是有效括号字符串原语。

对S进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S。



示例 1：

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-outermost-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <string>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    string removeOuterParentheses(string S) {
        /**
         * 当左右的括号数量相等时，就是一个元语，且元语是对称的
         */
        if (S.empty()) return S;
        int left = 0, right = 0;
        queue<char> parQueue;  // 用队列比栈舒服
        string ans;
        for (const auto &x:S) {
            if (x == '(') {
                ++left;
                parQueue.push(x);
            } else if (x == ')') {
                ++right;
                parQueue.push(x);
            }
            if (left == right) {
                parQueue.pop(); // 去除左外围
                --right;
                for (int i = left + right; i > 1; --i) {
                    ans.push_back(parQueue.front());
                    parQueue.pop();
                }
                parQueue.pop(); // 去除右外围
                left = right = 0;
            }

        }
//        reverse(ans.begin(),ans.end());
        return ans;
    }

    string removeOuterParentheses2(string S) {
        // 通过计数器的值实时判断该括号是否有效
        string ans;
        int count = 0;
        for (const auto &x:S) {
            if (x == '(' and count++ > 0) ans.push_back(x);
            if (x == ')' and count-- > 1) ans.push_back(x);
        }
        return ans;

    }

};

int main() {
    Solution sol;
    cout << sol.removeOuterParentheses("(()())(())") << endl;
    cout << sol.removeOuterParentheses2("(()())(())(()(()))") << endl;
}